<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>【LCA练习 倍增 tarjin】 洛谷P3379【模板】最近公共祖先 P1967货车运输.md | 蓝湖畔淅淅沥沥的雨</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。 倍增 构造O(nlogn)，在线(单次)查询O(logn) tarjin 构造O(n) ，离线(全部">
<meta property="og:type" content="article">
<meta property="og:title" content="【LCA练习 倍增 tarjin】 洛谷P3379【模板】最近公共祖先 P1967货车运输.md">
<meta property="og:url" content="http://example.com/1111/11/11/%E3%80%90LCA%E7%BB%83%E4%B9%A0%20%E5%80%8D%E5%A2%9E%20tarjin%E3%80%91%20%E6%B4%9B%E8%B0%B7P3379%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%20P1967%E8%B4%A7%E8%BD%A6%E8%BF%90%E8%BE%93/index.html">
<meta property="og:site_name" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。 倍增 构造O(nlogn)，在线(单次)查询O(logn) tarjin 构造O(n) ，离线(全部">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="1111-11-11T03:06:11.000Z">
<meta property="article:modified_time" content="2022-05-06T07:16:59.707Z">
<meta property="article:author" content="StarsWhisper">
<meta property="article:tag" content="OldBlog(Before20220505)">
<meta property="article:tag" content="LCA">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="蓝湖畔淅淅沥沥的雨" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

  
<link rel="stylesheet" href="/plugin/bganimation/bg.css">

  

  <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">
<meta name="generator" content="Hexo 6.1.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <div class="outer">
        <div class="widget-wrap mobile-header">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

        <section id="main"><article id="post-【LCA练习 倍增 tarjin】 洛谷P3379【模板】最近公共祖先 P1967货车运输" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90LCA%E7%BB%83%E4%B9%A0%20%E5%80%8D%E5%A2%9E%20tarjin%E3%80%91%20%E6%B4%9B%E8%B0%B7P3379%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%20P1967%E8%B4%A7%E8%BD%A6%E8%BF%90%E8%BE%93/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      【LCA练习 倍增 tarjin】 洛谷P3379【模板】最近公共祖先 P1967货车运输.md
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%9B%BE%E8%AE%BA/">图论</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<p>倍增 构造O(nlogn)，在线(单次)查询O(logn)<br />
tarjin 构造O(n) ，离线(全部)查询O(N+M)<br />
根据题目 <strong>洛谷P3379【模板】最近公共祖先</strong> 的样例测试，tarjin和倍增不能通过占用的时间或空间评判高下，谁占优势应该跟数据的特征有关。</p>
<h2 id="洛谷p3379模板最近公共祖先"><a class="markdownIt-Anchor" href="#洛谷p3379模板最近公共祖先"></a> 洛谷P3379【模板】最近公共祖先</h2>
<p>倍增方法</p>
<blockquote>
<p>构造fa数组的正确写法是这样的<br />
for(int i=1; i&lt;=20; i++){<br />
fa[x][i] = fa[fa[x][i-1]][i-1];<br />
}<br />
然而第一遍错写成了这样<br />
for(int i=1; i&lt;=20; i++){<br />
fa[x][i] = fa[father][i-1];<br />
}<br />
这显然是错误的，不是方法他的父亲的上2<sup>i-1个节点，而是访问它的上2</sup>i-1个节点的上2^i-1个节点<br />
引以为戒</p>
</blockquote>
<pre><code>#include &lt;iostream&gt;
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;queue&gt;
#include &lt;map&gt;
#include &lt;stack&gt;
#include &lt;string&gt;
#include &lt;cstring&gt;
#include &lt;vector&gt;
#include &lt;cmath&gt;
#include &lt;set&gt;
typedef long long int LL;
const int N = 5e5+5;
int fa[N][22],depth[N],head[N];
int n,m,s,u,v;
int idx;
struct Edge
&#123;
    int to,nxt;
&#125;edg[N&lt;&lt;1];
void addEdge(int fr,int to)
&#123;
    edg[idx].to = to;
    edg[idx].nxt = head[fr];
    head[fr] = idx++;
&#125;
void build(int x,int father)
&#123;
    fa[x][0] = father;
    depth[x] = depth[father]+1;
    for(int i=1; i&lt;=20; i++)&#123;
        fa[x][i] = fa[fa[x][i-1]][i-1];
    &#125;
    for(int e=head[x]; e; e=edg[e].nxt)&#123;
        int y = edg[e].to;
        if(y!=father) build(y,x);
    &#125;
&#125;
int lca(int x,int y)
&#123;
    if(depth[x] &lt; depth[y]) std::swap(x,y);
    for(int i=20; i&gt;=0; i--)&#123;
        if(fa[x][i]) if(depth[fa[x][i]]&gt;=depth[y])&#123;
            x = fa[x][i];
            if(depth[x] == depth[y]) break;
        &#125;
    &#125;
    if(x == y) return x;
    for(int i=20; i&gt;=0; i--)&#123;
        if(fa[x][i]) if(fa[x][i] != fa[y][i])&#123;
            x = fa[x][i];
            y = fa[y][i];
        &#125;
    &#125;
    return fa[y][0];
&#125;
int main()
&#123;
    //freopen(&quot;D:\\EdgeDownloadPlace\\P3379_2.in&quot;,&quot;r&quot;,stdin);
    idx = 2;
    scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;s);
    for(int i=1; i&lt;n; i++)&#123;
        scanf(&quot;%d%d&quot;,&amp;u,&amp;v);
        addEdge(u,v); addEdge(v,u);
    &#125;
    build(s,0);
    for(int i=0; i&lt;m; i++)&#123;
        scanf(&quot;%d%d&quot;,&amp;u,&amp;v);
        printf(&quot;%d\n&quot;,lca(u,v));
    &#125;
    return 0;
&#125;
</code></pre>
<p>倍增方法可以提前算log优化</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <algorithm><br />
​    #include <queue><br />
​    #include <map><br />
​    #include <stack><br />
​    #include <string><br />
​    #include <cstring><br />
​    #include <vector><br />
​    #include <cmath><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int N = 5e5+5;<br />
​    int fa[N][22],depth[N],head[N],old_brother[N];<br />
​    int n,m,s,u,v;<br />
​    int idx;<br />
​    struct Edge<br />
​    {<br />
​        int to,nxt;<br />
​    }edg[N&lt;&lt;1];<br />
​    void addEdge(int fr,int to)<br />
​    {<br />
​        edg[idx].to = to;<br />
​        edg[idx].nxt = head[fr];<br />
​        head[fr] = idx++;<br />
​    }<br />
​    void build(int x,int father)<br />
​    {<br />
​        fa[x][0] = father;<br />
​        depth[x] = depth[father]+1;<br />
​<br />
​        for(int i=1; i&lt;=old_brother[depth[x]]; i++){<br />
​        //for(int i=1; i&lt;=20; i++){<br />
​            fa[x][i] = fa[fa[x][i-1]][i-1];<br />
​        }<br />
​<br />
for(int e=head[x]; e; e=edg[e].nxt){<br />
int y = edg[e].to;<br />
if(y!=father) build(y,x);<br />
}<br />
}<br />
int lca(int x,int y)<br />
{<br />
if(depth[x] &lt; depth[y]) std::swap(x,y);<br />
//<br />
/*<br />
for(int i=20; i&gt;=0; i–){<br />
if(fa[x][i]) if(depth[fa[x][i]]&gt;=depth[y]){<br />
x = fa[x][i];<br />
if(depth[x] == depth[y]) break;<br />
}<br />
}<br />
*/<br />
while(depth[x] &gt; depth[y]){<br />
x = fa[x][old_brother[depth[x]-depth[y]]-1];<br />
}<br />
///<br />
if(x == y) return x;<br />
for(/<em>int i=20;</em>/ int i=old_brother[depth[x]]-1; i&gt;=0; i–){<br />
if(fa[x][i] != fa[y][i]){<br />
x = fa[x][i];<br />
y = fa[y][i];<br />
}<br />
}<br />
return fa[y][0];<br />
}<br />
int main()<br />
{<br />
//freopen(“D:\EdgeDownloadPlace\P3379_2.in”,“r”,stdin);<br />
idx = 2;<br />
scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;s);<br />
for(int i=1; i&lt;n; i++){<br />
scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
addEdge(u,v); addEdge(v,u);<br />
}<br />
for(int i=1; i&lt;=n; i++){<br />
old_brother[i] = old_brother[i-1] + (1 &lt;&lt; old_brother[i-1] == i);<br />
}<br />
build(s,0);<br />
for(int i=0; i&lt;m; i++){<br />
scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
printf(&quot;%d\n&quot;,lca(u,v));<br />
}<br />
return 0;<br />
}</p>
<p>​</p>
<p>tarjin方法</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstring><br />
​    #include <string><br />
​    #include <cstdlib><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <queue><br />
​    #include <stack><br />
​    #include <vector><br />
​    #include <set><br />
​    #include <map><br />
​    typedef long long int LL;<br />
​    //typedef std::pair&lt;int ,int&gt; PP;<br />
​    const int N = 5e5+5, M = 1e6+5, INF = 0x7fffffff;<br />
​    int n, m, u, v, s;<br />
​    int idx,qidx;<br />
​    int head[N],sset[N],vis[N],ans[N],qhead[N];<br />
​    struct Edge<br />
​    {<br />
​        int to, nxt;<br />
​    } edg[M];<br />
​    struct QEdge<br />
​    {<br />
​        int to, nxt, id;<br />
​    } qedg[M];<br />
​    void initial()<br />
​    {<br />
​        idx = qidx = 2;<br />
​        for (int i = 0; i &lt; N; i++)<br />
​            sset[i] = i;<br />
​    }<br />
​    int ffind(int x)<br />
​    {<br />
​        return sset[x] == x ? x : sset[x] = ffind(sset[x]);<br />
​    }<br />
​    void mmerge(int x,int  y)<br />
​    {<br />
​        sset[ffind(x)] = ffind(y);<br />
​    }<br />
​    void addEdge(int fr,int to)<br />
​    {<br />
​        edg[idx].to = to;<br />
​        edg[idx].nxt = head[fr];<br />
​        head[fr] = idx++;<br />
​    }<br />
​    void qaddEdge(int fr,int to,int id)<br />
​    {<br />
​        qedg[qidx].to = to;<br />
​        qedg[qidx].nxt = qhead[fr];<br />
​        qedg[qidx].id = id;<br />
​        qhead[fr] = qidx++;<br />
​    }<br />
​    void tarjin(int x,int fr)<br />
​    {<br />
​        for (int e = head[x]; e; e=edg[e].nxt){<br />
​            if((e^1) == fr)<br />
​                continue;<br />
​            int y = edg[e].to;<br />
​            tarjin(y,e);<br />
​            mmerge(y, x);<br />
​        }<br />
​        for (int e = qhead[x]; e; e=qedg[e].nxt){<br />
​            int y = qedg[e].to;<br />
​            if(vis[y])<br />
​                ans[qedg[e].id] = ffind(y);<br />
​        }<br />
​        vis[x] = 1;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        initial();<br />
​        scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;s);<br />
​        for (int i = 1; i &lt; n; i++){<br />
​            scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
​            addEdge(u, v);<br />
​            addEdge(v, u);<br />
​        }<br />
​        for (int i = 0; i &lt; m; i++){<br />
​            scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
​            qaddEdge(u, v, i);<br />
​            qaddEdge(v, u, i);<br />
​        }<br />
​        tarjin(s,0);<br />
​        for (int i = 0; i &lt; m; i++)<br />
​            printf(&quot;%d\n&quot;,ans[i]);<br />
​        return 0;<br />
​    }</p>
<h2 id="洛谷-p1967-noip2013-提高组-货车运输"><a class="markdownIt-Anchor" href="#洛谷-p1967-noip2013-提高组-货车运输"></a> 洛谷 P1967 [NOIP2013 提高组] 货车运输</h2>
<p>最大生成树 + 倍增lca找最短距离<br />
注意应该先更新ans，再使当前点倍增跳跃，刚才是有一处写反了，没注意到，导致WA</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstdlib><br />
​    #include <cstring><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <string><br />
​    #include <queue><br />
​    #include <vector><br />
​    #include <stack><br />
​    #include <map><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int N = 1e4+4, M = 5e4+4, INF = 0x7fffffff, LM = 14;<br />
​    int n,m,u,v,w,k,ans;<br />
​    int idx;<br />
​    int head[N],sset[N],fa[N][LM+1],dis[N][LM+1],depth[N],vis[N];<br />
​    struct Esave<br />
​    {<br />
​        int fr,to,w;<br />
​    }es[M&lt;&lt;1];<br />
​    struct Edge<br />
​    {<br />
​        int to,nxt,w;<br />
​    }edg[M&lt;&lt;1];<br />
​    void addE(int u,int v,int w)<br />
​    {<br />
​        edg[idx].to = v;<br />
​        edg[idx].nxt = head[u];<br />
​        edg[idx].w = w;<br />
​        head[u] = idx++;<br />
​    }<br />
​    void initial()<br />
​    {<br />
​        idx = 2;<br />
​        for(int i=0; i&lt;N; i++) sset[i] = i;<br />
​    }<br />
​    bool escmp(Esave x,Esave y)<br />
​    {<br />
​        return x.w &gt; y.w;<br />
​    }<br />
​    int ffind(int x)<br />
​    {<br />
​        return sset[x] == x ? x : sset[x] = ffind(sset[x]);<br />
​    }<br />
​    void mmerge(int x,int y)<br />
​    {<br />
​        sset[ffind(x)] = ffind(y);<br />
​    }<br />
​    void build(int x,int father,int d)<br />
​    {<br />
​        fa[x][0] = father;<br />
​        dis[x][0] = d;<br />
​        depth[x] = depth[father] + 1;<br />
​        for(int i=1; i&lt;=LM; i++){<br />
​            fa[x][i] = fa[fa[x][i-1]][i-1];<br />
​            dis[x][i] = std::min(dis[fa[x][i-1]][i-1],dis[x][i-1]);<br />
​        }<br />
​        for(int e=head[x]; e; e=edg[e].nxt){<br />
​            if(edg[e].to != father) build(edg[e].to,x,edg[e].w);<br />
​        }<br />
​    }<br />
​    int lca(int x,int y)<br />
​    {<br />
​        ans = INF;<br />
​        if(ffind(x) != ffind(y)) return -1;<br />
​        if(depth[x] &lt; depth[y]) std::swap(x,y);<br />
​        for(int i=LM; i&gt;=0; i–){<br />
​            if(fa[x][i]) if(depth[fa[x][i]] &gt;= depth[y]){<br />
​                ans = std::min(ans,dis[x][i]);<br />
​                x = fa[x][i];<br />
​            }<br />
​            if(depth[x] == depth[y]) break;<br />
​        }<br />
​        if(x == y) return ans;<br />
​        for(int i=LM; i&gt;=0; i–){<br />
​            if(fa[x][i]) if(fa[x][i] != fa[y][i]){<br />
​                ans = std::min(ans,dis[x][i]);<br />
​                ans = std::min(ans,dis[y][i]);<br />
​                x = fa[x][i];<br />
​                y = fa[y][i];<br />
​            }<br />
​        }<br />
​        return std::min(ans,std::min(dis[x][0],dis[y][0]));<br />
​        //return ans;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        initial();<br />
​        scanf(&quot;%d%d&quot;,&amp;n,&amp;m);<br />
​        for(int i=0; i&lt;m; i++) scanf(&quot;%d%d%d&quot;,&amp;es[i].fr,&amp;es[i].to,&amp;es[i].w);<br />
​        std::sort(es,es+m,escmp);<br />
​        for(int i=0; i&lt;m;  i++){<br />
​            u = es[i].fr, v = es[i].to, w = es[i].w;<br />
​            if(ffind(u) != ffind(v)){<br />
​                mmerge(u,v);<br />
​                addE(u,v,w); addE(v,u,w);<br />
​            }<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++) if(!vis[ffind(i)]){<br />
​            vis[ffind(i)] = 1;<br />
​            build(i,0,0);<br />
​        }<br />
​        scanf(&quot;%d&quot;,&amp;k);<br />
​        while(k–){<br />
​            scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
​            printf(&quot;%d\n&quot;,lca(u,v));<br />
​        }<br />
​        return 0;<br />
​    }</p>
<p>求log优化版</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstdlib><br />
​    #include <cstring><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <string><br />
​    #include <queue><br />
​    #include <vector><br />
​    #include <stack><br />
​    #include <map><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int N = 1e4+4, M = 5e4+4, INF = 0x7fffffff, LM = 14;<br />
​    int n,m,u,v,w,k,ans;<br />
​    int idx;<br />
​    int head[N],sset[N],fa[N][LM+1],dis[N][LM+1],depth[N],vis[N],lg[N];<br />
​    struct Esave<br />
​    {<br />
​        int fr,to,w;<br />
​    }es[M&lt;&lt;1];<br />
​    struct Edge<br />
​    {<br />
​        int to,nxt,w;<br />
​    }edg[M&lt;&lt;1];<br />
​    void addE(int u,int v,int w)<br />
​    {<br />
​        edg[idx].to = v;<br />
​        edg[idx].nxt = head[u];<br />
​        edg[idx].w = w;<br />
​        head[u] = idx++;<br />
​    }<br />
​    void initial()<br />
​    {<br />
​        idx = 2;<br />
​        for(int i=0; i&lt;N; i++) sset[i] = i;<br />
​        for(int i=1; i&lt;N; i++) lg[i] = lg[i-1] + (1 &lt;&lt; lg[i-1] == i);<br />
​    }<br />
​    bool escmp(Esave x,Esave y)<br />
​    {<br />
​        return x.w &gt; y.w;<br />
​    }<br />
​    int ffind(int x)<br />
​    {<br />
​        return sset[x] == x ? x : sset[x] = ffind(sset[x]);<br />
​    }<br />
​    void mmerge(int x,int y)<br />
​    {<br />
​        sset[ffind(x)] = ffind(y);<br />
​    }<br />
​    void build(int x,int father,int d)<br />
​    {<br />
​        fa[x][0] = father;<br />
​        dis[x][0] = d;<br />
​        depth[x] = depth[father] + 1;<br />
​        for(int i=1; i&lt;=lg[depth[x]]-1; i++){<br />
​            fa[x][i] = fa[fa[x][i-1]][i-1];<br />
​            dis[x][i] = std::min(dis[fa[x][i-1]][i-1],dis[x][i-1]);<br />
​        }<br />
​        for(int e=head[x]; e; e=edg[e].nxt){<br />
​            if(edg[e].to != father) build(edg[e].to,x,edg[e].w);<br />
​        }<br />
​    }<br />
​    int lca(int x,int y)<br />
​    {<br />
​        ans = INF;<br />
​        if(ffind(x) != ffind(y)) return -1;<br />
​        if(depth[x] &lt; depth[y]) std::swap(x,y);<br />
​        /*<br />
​        for(int i=LM; i&gt;=0; i–){<br />
​            if(fa[x][i]) if(depth[fa[x][i]] &gt;= depth[y]){<br />
​                ans = std::min(ans,dis[x][i]);<br />
​                x = fa[x][i];<br />
​            }<br />
​            if(depth[x] == depth[y]) break;<br />
​        }<br />
​        <em>/<br />
​        *<br />
​        while(depth[x] &gt; depth[y]){<br />
​            u = lg[depth[x]-depth[y]]-1;<br />
​            ans = std::min(ans,dis[x][u]);<br />
​            x = fa[x][u];<br />
​        }<br />
​        //</em>/<br />
​        if(x == y) return ans;<br />
​        for(int i=lg[depth[x]]-1; i&gt;=0; i–){<br />
​            if(fa[x][i]) if(fa[x][i] != fa[y][i]){<br />
​                ans = std::min(ans,dis[x][i]);<br />
​                ans = std::min(ans,dis[y][i]);<br />
​                x = fa[x][i];<br />
​                y = fa[y][i];<br />
​            }<br />
​        }<br />
​        return std::min(ans,std::min(dis[x][0],dis[y][0]));<br />
​        //return ans;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        initial();<br />
​        scanf(&quot;%d%d&quot;,&amp;n,&amp;m);<br />
​        for(int i=0; i&lt;m; i++) scanf(&quot;%d%d%d&quot;,&amp;es[i].fr,&amp;es[i].to,&amp;es[i].w);<br />
​        std::sort(es,es+m,escmp);<br />
​        for(int i=0; i&lt;m;  i++){<br />
​            u = es[i].fr, v = es[i].to, w = es[i].w;<br />
​            if(ffind(u) != ffind(v)){<br />
​                mmerge(u,v);<br />
​                addE(u,v,w); addE(v,u,w);<br />
​            }<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++) if(!vis[ffind(i)]){<br />
​            vis[ffind(i)] = 1;<br />
​            build(i,0,0);<br />
​        }<br />
​        scanf(&quot;%d&quot;,&amp;k);<br />
​        while(k–){<br />
​            scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
​            printf(&quot;%d\n&quot;,lca(u,v));<br />
​        }<br />
​        return 0;<br />
​    }</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90LCA%E7%BB%83%E4%B9%A0%20%E5%80%8D%E5%A2%9E%20tarjin%E3%80%91%20%E6%B4%9B%E8%B0%B7P3379%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%20P1967%E8%B4%A7%E8%BD%A6%E8%BF%90%E8%BE%93/" data-id="cl2uhoeby0018e4j3como9hfl" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/LCA/" rel="tag">LCA</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/1111/11/11/%E3%80%90KM%E7%AE%97%E6%B3%95%E3%80%91B%20-%20Going%20Home%20POJ%20-%202195/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">上一篇</strong>
      <div class="article-nav-title">
        
          【KM算法】B - Going Home POJ - 2195.md
        
      </div>
    </a>
  
  
    <a href="/1111/11/11/%E3%80%90Trie%E6%A0%91&AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E3%80%91P3879%5BTJOI2010%5D%E9%98%85%E8%AF%BB%E7%90%86%E8%A7%A3%20P3808%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E7%AE%80%E5%8D%95%E7%89%88%EF%BC%89P3796%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E5%8A%A0%E5%BC%BA%E7%89%88%EF%BC%89/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">下一篇</strong>
      <div class="article-nav-title">【Trie树&amp;AC自动机】P3879[TJOI2010]阅读理解 P3808 【模板】AC自动机（简单版）P3796 【模板】AC自动机（加强版）.md</div>
    </a>
  
</nav>

  
</article>



</section>
        
          <aside id="sidebar">
  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <h1 class="blog-title">蓝湖畔淅淅沥沥的雨</h1>
    <h2 class="blog-subtitle">All tragedy erased, I see only wonders...</h2>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>



    <div class="social-link">
      
        <a class="hvr-bounce-in" href="https://github.com/Wldcmzy" target="_blank" title="Github">
          Github
        </a>
      
        <a class="hvr-bounce-in" href="https://blog.csdn.net/wldcmzy" target="_blank" title="CSDN">
          CSDN
        </a>
      
        <a class="hvr-bounce-in" href="https://space.bilibili.com/83743701" target="_blank" title="bilibili(无技术和学习内容)">
          bilibili(无技术和学习内容)
        </a>
      
    </div>

    <div class="friend-link">
      <h2>友情链接</h2>
      
        <a class="hvr-bounce-in" href="https://shanamaid.github.io/" target="_blank" title="夏娜主题作者的博客">
          夏娜主题作者的博客
        </a>
      
    </div>
  </div>
</div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy;2021 - 2022 StarsWhisper<br>
      由<a href="http://hexo.io/" target="_blank">Hexo</a>强力驱动 | 
      主题-<a target="_blank" rel="noopener" href="https://github.com/ShanaMaid/hexo-theme-shana">Shana</a>(但是魔改)
      
    </div>
    
  </div>
</footer>
    </div>
    

<script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
<script src="//apps.bdimg.com/libs/wow/0.1.6/wow.min.js"></script>
<script>
new WOW().init();
</script>   


  
<link rel="stylesheet" href="/plugin/fancybox/jquery.fancybox.css">

  
<script src="/plugin/fancybox/jquery.fancybox.pack.js"></script>




  
<link rel="stylesheet" href="/plugin/galmenu/GalMenu.css">

  
<script src="/plugin/galmenu/GalMenu.js"></script>

  <div class="GalMenu GalDropDown">
      <div class="circle" id="gal">
        <div class="ring">
          
            <a href="/announcement" title="" class="menuItem">公告</a>
          
            <a href="/tags" title="" class="menuItem">标签</a>
          
            <a href="/categories" title="" class="menuItem">分类</a>
          
            <a href="/archives" title="" class="menuItem">归档</a>
          
            <a href="/knightabout" title="" class="menuItem">关于</a>
          
            <a href="/bridges" title="" class="menuItem">传送门</a>
          
        </div>
        
          <audio id="audio" src="#"></audio>
        
      </div> 
</div>
<div id="overlay" style="opacity: 1; cursor: pointer;"></div>
  <script type="text/javascript">var items = document.querySelectorAll('.menuItem');
    for (var i = 0,
    l = items.length; i < l; i++) {
      items[i].style.left = (50 - 35 * Math.cos( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%";
      items[i].style.top = (50 + 35 * Math.sin( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%"
    }</script>
<script type="text/javascript">
  $(document).ready(function() {
    $('body').GalMenu({
      'menu': 'GalDropDown'
    })
  });
</script>

  <section class="hidden-xs"> 
  <ul class="cb-slideshow"> 
    <li><span>苟利</span></li> 
    <li><span>国家</span></li> 
    <li><span>生死以</span></li> 
    <li><span>岂能</span></li> 
    <li><span>祸福</span></li> 
    <li><span>趋避之</span></li> 
  </ul>
</section>

<script src="/js/script.js"></script>




  </div>
</body>
</html>